package org.demo.sorting;

public class ListInsertSort implements Sort {

	public Node sort(Node node) {
		Node t, x;
		Node b = new Node(0, null);
		while (node.next != null) {
			t = node.next;
			node.next = t.next;
			for (x = b; x.next != null; x = x.next)
				if (x.next.val > t.val)
					break;
			t.next = x.next;
			x.next = t;
		}
		return b;
	}
}
